"""
题目：判断图中是否存在从指定起点到终点的路径。
"""


class Graph:
    def __init__(self, is_directed=False):
        self.vertices = {}
        self.is_directed = is_directed

    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.vertices[v1].append(v2)
        if not self.is_directed:
            self.vertices[v2].append(v1)

    def has_path(self, start, end):
        """使用DFS判断是否存在从start到end的路径"""
        # 起点或终点不存在于图中
        if start not in self.vertices or end not in self.vertices:
            return False

        # 起点和终点相同
        if start == end:
            return True

        visited = set()  # 避免循环访问

        def dfs(current):
            # 如果找到终点，返回True
            if current == end:
                return True

            visited.add(current)

            # 遍历所有邻接顶点
            for neighbor in self.vertices[current]:
                if neighbor not in visited:
                    # 递归检查邻接顶点
                    if dfs(neighbor):
                        return True

            # 所有路径都检查过，未找到终点
            return False

        return dfs(start)


# 测试
graph = Graph(is_directed=True)
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')
graph.add_edge('C', 'D')
graph.add_edge('B', 'E')

print(graph.has_path('A', 'D'))  # 输出: True (A->B->C->D)
print(graph.has_path('A', 'F'))  # 输出: False (F不在图中)
print(graph.has_path('E', 'A'))  # 输出: False (有向图，E到A没有边)
